package my.study.java.basic.algorithm.sorts;

import java.util.Random;
/**
 * 冒泡排序对n个元素的序列进行n - 1次扫描，在每次扫描中，
 * 它对从左到右相邻的两个元素进行比较，如果它们不符合顺序，
 * 就将他们交换位置
 * T(n) = O(n^2) 
 * 
 * @author fanhongjie
 * 
 */
public class BubbleSort {
	private static final int N = 9;
	public static void main(String[] args) {
		Element array[] = new Element[N];
		Random random = new Random();
		for (int i = 0; i < N; i++) {
			array[i] = new Element(random.nextInt(2 * N)); 
		}
		System.out.print("Init:\t");
		for (int i = 0; i < N; i++) {
			System.out.print(array[i].getValue() + "\t");
		}
		System.out.println();
		//Bubble Sort()
		for (int i = N - 1; i > 0; i--) {
			for (int j = 1; j <= i; j++) {
				if (array[j].compareTo(array[j - 1]) < 0) {
					Element o = array[j];
					array[j] = array[j - 1];
					array[j - 1] = o;
				}
			}
			System.out.print((N - i) + ":\t");
			for (int k = 0; k < N; k++) {
				System.out.print(array[k].getValue() + "\t");
			}
			System.out.println();
		}
		
		System.out.print("Result:\t");
		for (int i = 0; i < N; i++) {
			System.out.print(array[i].getValue() + "\t");
		}
		System.out.println();
	}

}
